An encoding technique for packet recovery and a decoding technique corresponding to the encoding technique have been increasingly important for wired or wireless network applications. The reason for this is that an increase in a data transfer speed brings about packet losses more often, while the conventional packet recovery method based on retransmission of packets increases performance overhead and buffer management overhead. Here, packet losses occur due to congestion attributed to errors in the detection of a header/synchronization pattern attributed to a temporary concentration of data packets at a network switch.
One prior art technique for solving the foregoing problems, encodes packets on a frame-by-frame basis using a block code such as an interleaved Reed Solomon (RS) erasure correcting code (Nonnenmacher, E. W. Biersack, and D. Towsley, “Parity-based loss recovery for reliable multicast,” IEEE/ACM Trans. Networking, vol. 6, pp. 349.361, August 1998.). In this conventional technique, however, a redundant packet is not used, and is just wasted when there are no lost packets in a given frame. This inefficiency can be reduced when a code length is set to be longer. At the same time, however longer code lengths result in an increase in the computational complexity for decoding.
As another prior art technique involves performing decoding by using a nonsystematic code specific to packet recovery, on the basis of a graph structure consisting of source nodes and check nodes which are commonly used by a sender and a receiver (Luby, M. Mitzenmacher, A. Shokrollahi, and D. Spielman, “Efficient erasure correcting codes,” IEEE Trans. Inform. Theory, vol. 47, pp. 569. 584, February 2001.). A non-systematic code is effective in terms of an encoding rate, and is efficient since it exhibits a substantially linear latency for decoding. Non-systematic codes, however, are not particularly efficient in terms of required bandwidth. Moreover, the efficiency of a hardware implementation of this method is similarly lacking due to random graph structures. For this reason, the application range of this method is limited to streaming media and data delivery for which encoding and decoding are implemented with software.
As still another conventional technique, there is a method for packet recovery using convolutional codes of (n, n−1, m) (M. Arai, A. Yamaguchi, K. Iwasaki, “Method to Recover Internet Packet Losses Using (n, n−1, m) Convolutional Codes,” IEEE Dependable System and Network, pp. 382-389, 2000.). In this method, a lost packet can be recovered more flexibly than a frame-based technique using block codes. Nevertheless, this method is based on a binary convolutional code, and thereby requires a loss correction on a bit-by-bit basis. For this reason, this method does not allow decoding on a symbol-by-symbol basis to be performed. Accordingly, it is necessary to arrange a large number of decoders in parallel rendering a costly hardware implementation in terms of area.
The foregoing conventional techniques for packet recovery suffer from inefficiencies related to longer code length, more complexity in implementation of a decoder circuit, etc. In addition, an excessive addition of redundant information may cause new congestion.